package sort.onlogn.my_quick_sort_test;

import java.util.Arrays;

/**
 * 基础版快排 待优化：当i == j时可以不交换 @see
 * @author yeyangtao created at 16:43 2020/12/10
 */
public class QuickSort1210 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 3, 6, 4, 5, 8, 2, 88, 44, 99};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort(int[] a, int start, int end) {
        if (start >= end) return;
        int p = partition(a, start, end);
        quickSort(a, start, p - 1);
        quickSort(a, p + 1, end);
    }

    private static int partition(int[] a, int start, int end) {
        int pivot = a[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (a[j] < pivot) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
        }
        a[end] = a[i];
        a[i] = pivot;
        return i;
    }
}
